1921. 消灭怪物的最大数量

Similar Question

Solution Tips

方案一: 贪心 + 模拟

在每个时刻，我们需要解决的怪物数量

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        int n = dist.size();
        vector<int> count(n, 0);  //对每只怪物的最迟消灭时间进行计数
        for(int i = 0; i < n; i++)
        {
            int time = (dist[i] - 1) / speed[i]; //怪物需要在time时间内被消灭
            if(time < n) //time >= n的怪物不用管
                count[time]++;
        }
        int kill = 0; //能够击杀怪物的数量
        for(int i = 0; i < n; i++)
        {
            kill++;  //每过一秒能多击杀一只怪物
            kill -= count[i];  //减去限定时间需要击杀的怪物
            if(kill < 0)  //如果怪物到达城市
                return i + 1;
        }
        return n;
    }
};

方案二: 官方题解

// 只想到了耿直模拟, 而且模拟难度也很高
// 第 i 分钟消灭的, 应该取决于第 i + 1 分钟, 怪物的位置, 需要消灭 最近的那个
// 感觉不对, 应该是要看整体的, 按照抵达城镇的先后顺序来击杀最合适.
// 抵达城镇需要 [1, 1, 2], 无法同时击杀 1 1 / 2 2 , 每个数字只能击杀一个
// const arrive = dist.map((d, i) => Math.ceil(d / speed[i])).sort((a, b) => a - b);
// 然后排序, 每次只能击杀一个 index, 有相同的就无法击杀了, 用跳过重复数去做, 返回 left
// 不是跳过重复数, 而是每个 index 只能击杀 index 个, 超出了就无法击杀
// 也不是 index index 的关系, 而是剩余攻击次数要大于 同一时刻到来的
var eliminateMaximum = function(dist, speed) {
    const n = dist.length;
    const arrivalTimes = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        arrivalTimes[i] = Math.ceil(dist[i] / speed[i]);
    }
    arrivalTimes.sort((a, b) => a - b);
    for (let i = 0; i < n; i++) {
        if (arrivalTimes[i] <= i) {
            return i;
        }
    }
    return n;
};